package com.shixianchen.review_the_day_before.day6;

import com.shixianjun.sort.Sortable;
import com.shixianjun.sort.SortableElement;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description 希尔排序
 * @date 2022/11/9 21:19
 */
public class ShellSort implements Sortable {

    @Override
    public void sort(SortableElement[] arr) {
        //搞一个变量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //希尔排序的本质是插入排序
            for (int i = gap; i < arr.length; i++) {
                //要插入的变量
                SortableElement insertValue = arr[i];
                //获取前一个变量的索引
                int j = i - gap;
                for (; j >= 0 && insertValue.value < arr[j].value; j-=gap) {
                    //将数据向前移
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = insertValue;
            }
        }

    }
}
